package arithmetic;

import java.lang.*;
import java.util.*;

/**
 * @Description: 二分查找（非递归实现）
 * @Author: renhai
 * @Date: 2022/3/15
 */
public class binary_search {

    /**
     * @param arr     数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 要查找的值
     * @return 如果找到就返回下标，如果没有找到，就返回 -1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        // 当 left > right 时，说明递归整个数组，但是没有找到
        if (left > right) {
            return -1;
        }
        int mid = left + (left - right) >> 1;
        int midVal = arr[mid];
        if (findVal > midVal) { // 向 右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { // 向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }

    }


    //   * 思路分析
//	 * 1. 在找到mid 索引值，不要马上返回
//	 * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
//	 * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
//	 * 4. 将Arraylist返回
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        /**
         * @Description: 查询多个重复的数
         * @param arr
         * @param left
         * @param right
         * @param findVal
         * @return: java.util.List<java.lang.Integer>
         * @Author: renhai
         * @Date: 2021/10/3
         */
        System.out.println("hello~");
        // 当 left > right 时，说明递归整个数组，但是没有找到
        if (left > right) {
            return new ArrayList<Integer>();
        }
        int mid = left + (left - right) >> 1;
        int midVal = arr[mid];

        if (findVal > midVal) { // 向 右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { // 向左递归
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
//			 * 思路分析
//			 * 1. 在找到mid 索引值，不要马上返回
//			 * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
//			 * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
//			 * 4. 将Arraylist返回

            List<Integer> resIndexlist = new ArrayList<>();
            //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {//退出
                    break;
                }
                //否则，就temp 放入到 resIndexlist
                resIndexlist.add(temp);
                temp -= 1; //temp左移
            }
            resIndexlist.add(mid);  //

            //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
                    break;
                }
                //否则，就temp 放入到 resIndexlist
                resIndexlist.add(temp);
                temp += 1; //temp右移
            }
            return resIndexlist;
        }

    }


    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int number;
        System.out.println("请输入要排序的个数:");
        number = in.nextInt();
        //直接插入排序
        int[] a = new int[number];
        for (int i = 0; i < number; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 1; i < a.length; ++i)//用end的位置控制边界
        {
            //单趟排序
            int end = i - 1;//下标减1 便于前面排好的数据与下标为i的数据进行比较
            int tmp = a[i];//设定中间变量储存值 便于后面插入
            while (end >= 0)//循环继续条件
            {
                if (a[end] > tmp) {
                    a[end + 1] = a[end];//将大的数据放到后面
                    end--;
                } else
                    break;
            }
            a[end + 1] = tmp;//插入数据数据或者保持不变

        }
        for (int element : a)
            System.out.println(element);
        int search_number;
        System.out.println("请输入你要查询的数据：");
        search_number = in.nextInt();
        boolean found = false;//判断能否找到
        int low = 0;//开始值
        int high = a.length - 1;//最大值
        int pos = 0;//位置设定
        while (low <= high && !found) {
            pos = (low + high) / 2;
            if (a[pos] == search_number) {
                found = true;//刚好找到
            } else if (a[pos] < search_number) {
                low = pos + 1;//后面一半查找
            } else {
                high = pos - 1;//前面一半查找
            }
        }
        if (found) {
            System.out.println("found at position on " + pos);
        } else {
            System.out.println("NO found");
        }

    }
}
